#include <iostream>
#include<functional>
#include<algorithm>

using namespace std;

template<class T>
int getmid(T* arr,int begin,int end)
{
    int mid = (begin+end)/2;
    if(arr[begin] < arr[end])
    {
        if(arr[begin] > arr[mid])
            return begin;
        else if(arr[mid] > arr[end])
            return end;
        else
            return mid;
    }
    else
    {
        if(arr[begin] < arr[mid])
            return begin;
        else if(arr[mid > arr[end]])
            return mid;
        else
            return end;
    }
    
}
//
//template<class T,class Compare>
//void myquick_sort(T* arr, int begin, int end,Compare com = greater<T>())
//{
//    //区间不存在
//    if(begin > end)
//        return;
//    
//    int left = begin;
//    int right = end;
//    int keyi = left;
//    
//    //左边为key，右边先走
//    //左边找大，右边找小
//    while(left < right)
//    {
//        while(left < right && com(arr[right],arr[keyi]))
//            right--;
//        while(left < right && !com(arr[left],arr[keyi]))
//            left++;
//        swap(arr[left],arr[right]);
//    }
//    swap(arr[left],arr[keyi]);
//    keyi = left;
//    
//    myquick_sort(arr, begin, keyi - 1,com);
//    myquick_sort(arr, keyi + 1, end,com);
//
//}

template<class RandomAccessIterator>
void myquick_sort(RandomAccessIterator begin,RandomAccessIterator end)
{
    //区间不存在
    if(begin > end)
        return;
    
    RandomAccessIterator left = begin;
    RandomAccessIterator right = end;
    RandomAccessIterator keyi = left;
    
    //左边为key，右边先走
    //左边找大，右边找小
    while(left < right)
    {
        while(left < right && *right >= *keyi)
            right--;
        while(left < right && *left <= *keyi)
            left++;
        swap(*right,*left);
    }
    swap(*left,*keyi);
    keyi = left;
    
    left = begin;
    right = end;
    myquick_sort(left, keyi - 1);
    myquick_sort(keyi + 1,right);

}

int main() 
{
    int arr[] = {4,6,2,1,8,9,3,5,7,7,6,4,4,2,1,2,3,5,11,10};
    
    for(auto& e : arr)
        cout << e << " ";
    cout << endl;
    myquick_sort(arr, 0, sizeof(arr) / sizeof(int),greater<int>());
    
    for(auto& e : arr)
        cout << e << " ";
    cout << endl;
    
    return 0;
}

